Cây nhị phân
Cây nhị phân

Cây nhị phân

Trong khoa học máy tính, cây nhị phân (tiếng Anh: binary tree) là một cấu trúc dữ liệu cây mà mỗi nút có nhiều nhất hai nút con, được gọi là con trái (left child) và con phải (right child). Một định nghĩa đệ quy chỉ sử dụng các khái niệm lý thuyết tập hợp là cây nhị phân không trống là một tuple (L, S, R), với L và R là các cây nhị phân hay tập hợp rỗng và S là tập đơn (singleton set).[1] Một số tác giả cho phép cây nhị phân cũng có thể là tập hợp trống.[2]Từ góc độ lý thuyết đồ thị, cây nhị phân (và K-ary) như định nghĩa ở đây thực sự là arborescence.[3] Vì vậy cây nhị phân có thể gọi là arborescence phân nhánh đôi (bifurcating arborescence)[3]—một thuật ngữ xuất hiện trong các sách lập trình rất cũ,[4] trước khi thuật ngữ khoa học máy tính hiện đại chiếm ưu thế. Cũng có thể hiểu cây nhị phân là một đồ thị vô hướng chứ không phải đồ thị có hướng, trong trường hợp đó cây nhị phân là một cây có gốcthứ tự[5] Một số tác giả dùng thuật ngữ cây nhị phân có gốc thay vì cây nhị phân để nhấn mạnh thực tế rằng cây có gốc, nhưng như được định nghĩa ở trên thì cây nhị phân luôn có gốc.[6] Cây nhị phân là trường hợp đặc biệt của cây K-ary, với k bằng 2.

Tài liệu tham khảo

WikiPedia: Cây nhị phân http://www.brpreiss.com/books/opus4/html/page355.h... http://www.cpphub.com/search/label/Binary%20trees http://piergiu.wordpress.com/2010/02/21/balanced-b... http://www.gamedev.net/page/resources/_/technical/... http://www.findstat.org/ http://www.findstat.org/BinaryTrees https://books.google.com/books?id=7XUSn0IKQEgC&pg=... https://books.google.com/books?id=WnkZSSc4IkoC&pg=... https://books.google.com/books?id=yI4Jx5Obr08C&pg=... https://commons.wikimedia.org/wiki/Category:C%C3%A...